package com.zofer.study.search;

/**
 * @description 二分查找 有序数组的相等的元素
 * @date: 2020/10/9 17:25
 * @author zofer
 */
public class EqualByBinarySearch {


    public static void main(String[] args) {
        int [] arr = {1,2,3,4,5,6,7,8};
        //非递归二分查找
//        System.out.println(binarySearchByNoRecursion(arr,3));
        //递归二分查找
        System.out.println(binarySearchByRecursion(arr,0,arr.length - 1,3));
    }


    /**
     * 递归二分查找
     */
    public static int binarySearchByRecursion(int [] arr,int start,int end,int target){
        if (target < arr[start] || arr[end] > target || start > end){
            return -1;
        }

        int mid = start + (end - start)/2;
        if (arr[mid] > target){
            end = mid -1;
            return binarySearchByRecursion(arr,start,end,target);
        }else if (arr[mid] < target){
            start = mid + 1;
            return binarySearchByRecursion(arr,start,end,target);
        }else {
            return mid;
        }
    }


    /**
     * 非递归二分查找
     */
    public static int binarySearchByNoRecursion(int [] arr,int target){
        int start = 0;
        int end = arr.length - 1;
        while (start <= end){
            int mid = start + (end - start)/2;
            if (arr[mid] > target){
                end = mid -1;
            }else if (arr[mid] < target){
                start = mid + 1;
            }else {
                return mid;
            }
        }
        return -1;
    }
}
